#define _CRT_SECURE_NO_WARNINGS

/*
READ THIS, AND THEN REPLACE THIS ENTIRE COMMENT WITH YOUR OWN
Replace everything here with an opening comment, in your own words,
describing the purpose of this program.  Include your name and ID
number in this comment.

By including your name in this file, you are confirming that you are
the author of the code that follows and that you have not copied code
from anyone else for this project.  Modifying, or making superficial
changes to someone else's code is not acceptable.  THIS IS IMPORTANT.
*/

#include <stdio.h>
#include <stdlib.h>
  
#define MAX_ROWS 100  // The maximum number of rows for any map
#define MAX_COLS 100  // The maximum number of cols for any map

#define FILENAME "map1.txt"  // The filename of the map



/* Every function must begin with a comment, including this one */
typedef struct{
	int dist;
	int row;
	int col;
	//int is_used;
}Position;

typedef struct{
	char letter;
	int row;
	int col;
}PosChar;

PosChar finish[26];
PosChar star[10000];

int l = 0;

typedef struct
{
	char letter;
	int row;
	int col;
	int dist;
	int index;
}PRINT_NODE;

PRINT_NODE print_array[26];
int print_array_size=0;

typedef struct{
	Position values[10000];
	int size;
}List;

List listPosition;

   
void InitList(List *b);
void addToList(List *b,Position p);
void RemoveFromList(List *b);
//void Finish(List *b, int *endRow,int *endCol,int *endDist);
int ListEmpty(List *b);
void RemoveWhenIntersect(List *b);

int main(void)
{
	char map[MAX_ROWS][MAX_COLS];
	FILE *fp;
	int i, j, ch, row, col;
	int a,c,d,e,f;
	int b=0;
	int endDist,endRow,endCol,addList,space;
	int tempCol,tempRow,tempDist;

	//set two another value to store the value in finish and star array
	int k = 0;
	/*int l = 0;*/
	//This part is for store character in the ListChar
	PosChar posStart;
	Position pos;



	//initial the position of start
	posStart.letter = 0;
	posStart.row = 0;
	posStart.col = 0;

	fp = fopen(FILENAME, "r");

	if(NULL == fp)
	{
		printf("Read file error!\n");
		return 0;
	}

	fscanf(fp, "%d", &row);
	fscanf(fp, "%d", &col);
	col = col - 1;

	for (i = 0; i <= row; i++){ 
		for (j = -1; j <= col; j++) {
			ch = fgetc(fp);
			if(ch == 64){
				posStart.letter = ch;
				posStart.row = i;
				posStart.col = j;
			}else if ((ch > 64) && (ch < 91)) {
				finish[k].row = i;
				finish[k].col = j;
				finish[k].letter = ch;
				k++;
			}else if(ch == 42){
				star[l].row = i;
				star[l].letter = ch;
				star[l].col = j;
				//printf("%d %d\n",star[l].row,star[l].col);
				l++;
			}
		}
	} 
	//printf("%d %d\n",star[l].row,star[l].col);

	printf("Starting position = (%d, %d)\n",posStart.row,posStart.col);

	InitList(&listPosition);

	//set the start position
	pos.col = posStart.col;
	pos.row = posStart.row;
	pos.dist = 0;
	addToList(&listPosition,pos);

	//printf("%d %d %d",listPosition.values[0].row,listPosition.values[0].col,listPosition.values[0].dist);

	//find the distance
	while (!ListEmpty(&listPosition)) {
		tempCol = listPosition.values[0].col;
		tempRow = listPosition.values[0].row;
		tempDist = listPosition.values[0].dist;
		
		for(a = 1;a <= 4;a++ ){
			if(a ==1){
				pos.col = tempCol + 1; 
				pos.row = tempRow;
				pos.dist = tempDist+1;
				addList =1;

					if(pos.col < col && pos.col>0 &&pos.row < row &&pos.row>0){
				
					for(d = 0;d<l;d++){
						if(pos.row == star[d].row && pos.col == star[d].col){
							addList = 0;	
						}
					}

					if(addList == 1){
						addToList(&listPosition, pos);
					}
				}
				
				
			}
			if(a == 2){
				
				pos.col = tempCol - 1;
				pos.row = tempRow;
				pos.dist = tempDist+1;
				addList =1;

				if(pos.col < col && pos.col>0 &&pos.row < row &&pos.row>0){
				
					for(d = 0;d<l;d++){
						
						if(pos.row == star[d].row && pos.col == star[d].col){
							addList = 0;	
						}
						//printf("%d\n",addList);
					}
					if(addList == 1){
						addToList(&listPosition,pos);
					}
				
				}
				
			}
			if(a ==3){
				
				pos.row = tempRow + 1;
				pos.col = tempCol;
				pos.dist = tempDist+1;
				addList =1;

				if(pos.col < col && pos.col>0 &&pos.row < row &&pos.row>0){
					
					for(d = 0;d<l;d++){
						//printf("%d %d\n",pos.row,pos.col);
						//printf("%d %d\n",star[d].row,star[d].col);
						if(pos.row == star[d].row && pos.col == star[d].col){
							addList = 0;
						}
					}
					if(addList == 1){
						//printf("%d\n",addList);
						addToList(&listPosition, pos);
					}
			}
				
			}
			if(a ==4){

				pos.row = tempRow - 1;
				pos.col = tempCol;
				pos.dist = tempDist+1;
				addList =1;

				if(pos.col < col && pos.col>0 &&pos.row < row &&pos.row>0){
				
				for(d = 0;d<l;d++){
					if(pos.row == star[d].row && pos.col == star[d].col){
						addList = 0;	
					}
				}
				if(addList == 1){
					addToList(&listPosition, pos);
				}
			}
			
			}
		}

		//star[l].row = listPosition.values[0].row;
		//star[l].col = listPosition.values[0].col;
		//star[l++].letter = '*';

		RemoveFromList(&listPosition);

	}
		

	
	return 0;
}

void InitList(List *b)
{
	b ->size =0;
	//printf("%d\n",b->size);
}

void addToList(List *b,Position p)
{

	int i;
	int list_size = b->size;
	for(i = 0; i != list_size; ++i)
	{
		if (b->values[list_size].row == p.row && b->values[list_size].col == p.col)
		{
			return ;
		}
	}

	//if(b->size == 0){
	b->values[list_size].row = p.row;
	b->values[list_size].col = p.col;
	b->values[list_size].dist = p.dist;
	b->size++;

	for (i = 0; i != 26; ++i)
	{
		if (p.row == finish[i].row && p.col == finish[i].col)
		{
			printf("Distance to %c (%d, %d) = %d\n", finish[i].letter, finish[i].row, finish[i].col, p.dist);
			print_array[print_array_size].letter = finish[i].letter;
			print_array[print_array_size].row =  finish[i].row;
			print_array[print_array_size].col = finish[i].col;
			print_array[print_array_size].dist =  p.dist;
			print_array[print_array_size].index = (int)letter;
			print_array_size++;

			finish[i].row = 0;
			finish[i].col = 0;

		}
	}

	star[l].row = listPosition.values[0].row;
	star[l].col = listPosition.values[0].col;
	star[l++].letter = '*';

	/*else{
		for(i = 0;i<a;i++){
			if(pos[i].col == p.col &&pos[i].row ==p.row){
				add =0;
			}
		}
		if(add == 1){
			b -> values[b->size].row = p.row;
			b -> values[b->size].col = p.col;
			b -> values[b->size].dist = p.dist;
			b->size++;
			pos[a] = p;
			a++;
		}
	}*/
	//printf("%d %d %d %d\n",b -> values[b->size-1].row,b -> values[b->size-1].col,b -> values[b->size-1].dist,b->size);
}

void RemoveFromList(List *b)
{
	int i;
	for(i = 0;i< b->size-1;i++){
		b->values[i].row = b->values[i+1].row;
		b->values[i].col = b->values[i+1].col;
		b->values[i].dist = b->values[i+1].dist;
	}
	b->size--;
}

void RemoveWhenIntersect(List *b)
{
	b->size--;
}

int ListEmpty(List *b)
{
	if(b->size == 0){
	return 1;
	}else{
		return 0;
	}
}